Leetcode - 99 Recover Binary Search Tree

Posted on | In ,

在Leetcode中碰到了从未在ACM中见过的Morris遍历，简单记录一下。

题目分析

题意是一棵二叉搜索树中，有两个节点顺序错了，需要我们进行还原。解决这道题的核心关键就在于，我们需要知道对于一棵二叉搜索树来说，它的中序遍历是有序的。那么我们就能将题目转换为，在一个数组中，将两个次序错误的元素还原。以下面的数组为例：

1 6 3 4 5 2 7

错误序列具有的特征是，对于6来说，6>3了。对于2来说，5>2了。所以我们会在序列中找到两个前一个大于后一个的颠倒元素。此时我们取第一次的第一个元素和第二次的后一个元素即可。对于基本的题目，这题只要递归中序遍历即可。但是Leetcode要求空间复杂度为O(1)，意味着递归是不符合要求的（递归是O(n)空间，考虑递归的栈有多深）。这里就引出了Morris遍历。

Morris遍历

令当前遍历的节点为cur

  1. 如果cur无左孩子，cur向右移动
  2. 如果cur有左孩子，找出cur 子树上最右的节点，记为mostRight
    1. 如果mostRight的右节点指向空，令其指向cur，cur向左节点移动
    2. 如果mostRight的右节点指向cur，令其为null，cur向右移动

我们对一棵树完整走一遍Morris遍历来加深印象。

Morris-1.png

我们从4节点开始遍历树。4有左儿子，mostRight为3。3右儿子指向null, 我们令其右儿子指向cur(4)，cur向左儿子移动变成2。

Morris-2.png

2节点有左儿子，mostRight为1。1的右节点指向null，我们令其右儿子指向cur(2)，cur向左儿子移动变成1.

Morris-3.png

3没有左儿子，向右移动到2.

Morris-4.png

我们又回到了2节点。2有左儿子，此时mostRight为1。注意到1的右儿子正指向cur(2)，所以令1的右儿子为NULL同时cur走向右儿子(3)。

Morris-5.png

3没有左儿子，向右移动到4。

Morris-6.png

此时cur为4，4有左儿子，mostRight为3。注意到3的右儿子指向cur，所以令3的右儿子为null。向右移动到5。这样整棵树就完成了遍历。只要将之前的解题思路和Morris遍历结合在一起，就完成了题目的要求。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *cur = root;
        TreeNode *pre = NULL, *first = NULL, *second = NULL;
        while (cur) {
            if (cur -> left != NULL) {
                TreeNode *mostRight = cur -> left;
                while (mostRight -> right != NULL && mostRight -> right != cur) {
                    mostRight = mostRight -> right;
                }
                if (mostRight -> right == NULL) {
                    mostRight -> right = cur;
                    cur = cur -> left;
                } else {
                    mostRight -> right = NULL;
                    if (pre != NULL && pre->val > cur ->val){
                        if(!first)first = pre;
                        second = cur;
                    }
                    pre = cur;
                    cur = cur -> right;
                }
            } else {
                if (pre != NULL && pre->val > cur ->val){
                    if(!first)first = pre;
                    second = cur;
                }
                pre = cur;
                cur = cur -> right;
            }
        }
        swap(first->val, second->val);
    }
};

参考文章

神级遍历——morris